import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
//        Solution solution = new Solution();
//        String s = "pwwkew";
//        System.out.println(solution.lengthOfLongestSubstring(s));
        Solution solution = new Solution();
        int[] nums = {1, 1, 1,2,2,3,4,5};
        int k = 5;
        System.out.println(solution.subarraySum2(nums, k)); // 输出：2
    }

    //无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        char[] charArray = s.toCharArray();
        if (charArray.length == 1) {
            return 1;
        }
        int max = 0;
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < charArray.length; i++) {
            for (int j = i; j < charArray.length; j++) {
                if (!set.contains(charArray[j])) {
                    set.add(charArray[j]);
                } else {
                    if (set.size() > max) {
                        max = set.size();
                    }
                    set.clear();
                    break;
                }
            }
        }
        return max;
    }

    // 和为 K 的子数组
    public int subarraySum(int[] nums, int k) {
        int count = 0; // 用于记录和为k的子数组个数
        int n = nums.length;

        // 枚举子数组的起始位置
        for (int i = 0; i < n; i++) {
            int sum = 0; // 当前子数组的和
            // 枚举子数组的结束位置
            for (int j = i; j < n; j++) {
                sum += nums[j]; // 计算从i到j的子数组和
                if (sum == k) {
                    count++; // 如果和为k，计数加1
                }
            }
        }

        return count;
    }

    public int subarraySum2(int[] nums, int k) {
        int count = 0; // 用于记录和为k的子数组个数
        int currentSum = 0; // 当前前缀和
        HashMap<Integer, Integer> prefixSumCount = new HashMap<>(); // 哈希表存储前缀和及其出现次数
        prefixSumCount.put(0, 1); // 初始化前缀和为0的情况

        for (int num : nums) {
            currentSum += num; // 更新当前前缀和
            // 检查是否存在前缀和为currentSum - k的情况
            if (prefixSumCount.containsKey(currentSum - k)) {
                count += prefixSumCount.get(currentSum - k); // 如果存在，计数加对应次数
            }
            // 更新哈希表中当前前缀和的出现次数
            prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
        }

        return count;
    }
}
